/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class CapacityToShipPackagesWithinDDays {
	public int shipWithinDays(int[] weights, int D) {
		int max = 0;
		int sum = 0;
		for (int i = 0; i < weights.length; i++) {
			max = Math.max(weights[i], max);
			sum += weights[i];
		}
		return binarySearch(max, sum, weights, D);
	}

	private int binarySearch(int left, int right, int[] a, int d) {
		while (left < right) {
			int mid = (left + right) / 2;
			int d2 = getDays(mid, a);
			if (d2 <= d) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}

		return left;
	}

	private int getDays(int mid, int[] a) {
		int res = 0;
		int sum = 0;
		for (int i = 0; i < a.length; i++) {
			sum += a[i];
			if (sum > mid) {
				sum = a[i];
				res++;
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
